// Written by Craig'n'Dave
using System;
using System.Collections.Generic;
// Quicksort using the Hoare partition scheme
namespace ConsoleApp1
{
    class Program
    {
        static List<string> quicksort(List<string> items)
        {
            // A single item does not need sorting
            if (items.Count <= 1)
            {
                return items;
            }
            else
            {
                // Set the two pointer positions and pivot to be the first item
                int pointer1 = 1;
                int pointer2 = items.Count - 1;
                string pivot_value = items[0];
                string temp;
                // Partitioning step
                while (pointer2 >= pointer1)
                {
                    // Move the first pointer
                    while ((pointer1 <= pointer2) && (string.Compare(items[pointer1], pivot_value) <= 0))
                    {
                        pointer1 = pointer1 + 1;
                    }
                    // Move the second pointer
                    while ((pointer2 >= pointer1) && (string.Compare(items[pointer2], pivot_value) >= 0))
                    {
                        pointer2 = pointer2 - 1;
                    }
                    // Swap items
                    if (pointer2 > pointer1)
                    {
                        temp = items[pointer1];
                        items[pointer1] = items[pointer2];
                        items[pointer2] = temp;
                    }
                }
                // Put the pivot in position
                temp = items[0];
                items[0] = items[pointer2];
                items[pointer2] = temp;

                // Divide and conquer left and right of the pivot
                List<string> new_list = new List<string>();
                new_list.AddRange(quicksort(items.GetRange(0, pointer2)));
                new_list.Add(items[pointer2]);
                new_list.AddRange(quicksort(items.GetRange(pointer2 + 1, items.Count - 1 - pointer2)));
                return new_list;
            }
        }

        // Main program starts here
        static void Main(string[] args)
        {
            List<string> items = new List<string> { "Florida", "Georgia", "Delaware", "Alabama", "California" };
            items = quicksort(items);
            Console.WriteLine(String.Join(", ", items));
        }
    }
}
